package Leetcode第二期;

/**
 * @author : K k
 * @date : 9:27 2020/10/11
 * 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
 *
 * 注意:
 *
 * 每个数组中的元素不会超过 100
 * 数组的大小不会超过 200
 * 示例 1:
 *
 * 输入: [1, 5, 11, 5]
 *
 * 输出: true
 *
 * 解释: 数组可以分割成 [1, 5, 5] 和 [11].
 *  
 *
 * 示例 2:
 *
 * 输入: [1, 2, 3, 5]
 *
 * 输出: false
 *
 * 解释: 数组不能分割成两个元素和相等的子集.
 */
public class 分割等和子集_416 {

    //01背包问题
    public boolean canPartition(int[] nums) {
        int len=nums.length;
        if (len==0){
            return false;
        }
        int sum=0;
        for (int num: nums){
            sum+=num;
        }
        if ((sum & 1)==1){
            //说明为基数
            return false;
        }
        int target=sum/2;

        //i代表 第i个数，j代表子数组的和 ture和false代表是否达到要求
        boolean[][] dp = new boolean[len][target + 1];
        if (nums[0]<=target){
            dp[0][0]=true;
        }
        for (int i=1; i<len;i++){
            for (int j=0;j<target;j++){
                dp[i][j]=dp[i-1][j];
                if (nums[i]==j){
                    //说明此时的子数组达到要求
                    dp[i][j]=true;
                    continue;
                }
                if (nums[i]<j){
                    //说明i-1之前的子数组可能找到部分元素，和为j-nums[i]
                    dp[i][j]=dp[i-1][j] || dp[i-1][j-nums[i]];
                }
            }
        }

        return dp[len-1][target];
    }
}
